from typing import List



class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 上下左右
        direction = [(0,1),(0,-1),(1,0),(-1,0)]


        l = len(word)
        h = len(board)
        w = len(board[0])
        flags = [[False for j in range(w)] for i in range(h)]
        def check(index_x,index_y,c) -> bool:
            # 如果不匹配返回false
            if board[index_x][index_y] != word[c]:
                return False
            if c == l-1 :
                return True
            flags[index_x][index_y] = True
            result = False
            for x,y in direction:
                # 判断边界
                new_x,new_y = index_x +x ,index_y+y
                if 0<=new_x <h and  0 <= new_y <w :
                    if flags[new_x][new_y] == False:
                        # c + 1 向下
                        if check(new_x,new_y,c+1):
                            result = True
                            break
            # 回退
            flags[index_x][index_y] = False
            # 如果成功  result 会为 True
            return result
        visited = set()
        for i in range(h):
            for j in range(w):
                if board[i][j] == word[0]:
                    if check(i,j,0):
                        return True
        return False


if __name__ == '__main__':
    board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
    word = "ABCB"
    solution = Solution()
    val = solution.exist(board,word)
    print(val)